#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>

using namespace std;

EdgeNode::EdgeNode(){
    this->dest = 0;
    this->link = nullptr;
}

EdgeNode::EdgeNode(int dest, EdgeNode* link){
    this->dest = dest;
    this->link = link;
}

EdgeNode::~EdgeNode(){

}

int EdgeNode::getDest(){
    return dest;
}

EdgeNode* EdgeNode::getNext(){
    return link;
}

void EdgeNode::setDest(int dest){
    this->dest = dest;
}

void EdgeNode::setNext(EdgeNode* link){
    this->link = link;
}

VertexNode::VertexNode(){
    this->data = '\0';
    this->firstEdge = nullptr;
}

VertexNode::VertexNode(char data, EdgeNode* firstEdge){
    this->data = data;
    this->firstEdge = firstEdge;
}

VertexNode::~VertexNode(){

}

char VertexNode::getData(){
    return data;
}

EdgeNode* VertexNode::getFirstEdge(){
    return firstEdge;
}

void VertexNode::setData(char data){
    this->data = data;
}

void VertexNode::setFirstEdge(EdgeNode* firstEdge){
    this->firstEdge = firstEdge;
}

MyGraph::MyGraph(){
    this->nodeNum = 0;
    this->edgeNum = 0;
    this->VexList = nullptr;
}

MyGraph::MyGraph(int nodeNum, int edgeNum, char* nodeList, int* edgeStartList, int* edgeEndList){//图的带参数初始化
    this->nodeNum = nodeNum;
    this->edgeNum = edgeNum;
    this->VexList = new VertexNode[nodeNum];
    for (int i = 0; i < nodeNum; i++)
    {
        this->VexList[i].setData(nodeList[i]);
    }
    for (int i = 0; i < edgeNum; i++)
    {
        int start = edgeStartList[i];
        int end = edgeEndList[i];

        EdgeNode* edge = new EdgeNode(end, this->VexList[start].getFirstEdge());
        this->VexList[start].setFirstEdge(edge);

        EdgeNode* edge1 = new EdgeNode(start, this->VexList[end].getFirstEdge());
        this->VexList[end].setFirstEdge(edge1);
    }
}

MyGraph::~MyGraph(){

}

int MyGraph::getNodeNum(){
    return nodeNum;
}

int MyGraph::getEdgeNum(){
    return edgeNum;
}

string MyGraph::printGraph(){
    string result = "";
    for (int i = 0; i < nodeNum; i++)
    {
        
        result += (VexList[i].getData()) ;
        result += ":";

        EdgeNode* edge = VexList[i].getFirstEdge();
        while (edge != nullptr)
        {            
            result += " ";
            result += (VexList[edge->getDest()].getData());

            edge = edge->getNext();
        }
        if (i != nodeNum - 1)
        {
            result += "\n";
        }   
    }
    return result;
}

int MyGraph::getFirstNeighbor(int v, int* visited){
    return 0;

}

int MyGraph::getNextNeighbor(int v, int w, int* visited){
    return 0;
}

void MyGraph::DFS(int v, int* visited, string& result){
    visited[v] = 1;
    EdgeNode *edge;
    result += this->VexList[v].getData();
    result += " ";
    edge = this->VexList[v].getFirstEdge();
    while (edge != nullptr)
    {
        if (visited[edge->getDest()] == 0)
        {
            DFS(edge->getDest(), visited, result);
        }
        edge = edge->getNext();
        
    }
}

string MyGraph::graph_DFS_Traverse(){
    int n = this->nodeNum;
    int* visited = new int[n];
    string result = "";
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            DFS(i, visited, result);
        }
        
    }
    return result;
}

void MyGraph::BFS(int v, int* visited, string& result){

}

string MyGraph::graph_BFS_Traverse(){
    int n = this->nodeNum;
    int* visited = new int[n];
    string result = "";
    EdgeNode* p;
    for (int i = 0; i < n; i++)
    {
        visited[i] = 0;
    }
    queue<int>q;
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            visited[i] = 1;
            result += this->VexList[i].getData();
            result += " ";
            q.push(i);

            while (!q.empty())
            {
                i = q.front();
                q.pop();
                p = this->VexList[i].getFirstEdge();
                while (p != nullptr)
                {
                    if (visited[p->getDest()] == 0)
                    {
                        visited[p->getDest()] = 1;
                        result += this->VexList[p->getDest()].getData();
                        result += " ";
                        q.push(p->getDest());
                    }
                    p = p->getNext();
                    
                }
                
            }
            
        }
        
    }
    return result;
}
